package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

//2Sum ,3Sum, 4Sum问题
public class Sum2Sum3Sum4 {

	public static void main(String[] args) {
//		int[] numbers = { 2, 1, 9, 4, 4, 56, 90, 3 };
//		int[] result = twoSum(numbers, 8);
//		System.out.println(result[0] + "  " + result[1]);
//		int[] nums = {1,-3,3,5,4,1};
//		System.out.println(threeSumClosest(nums, 1));
		
//		int[] S = {0, 0, 0, 0};
//		System.out.println(fourSum(S, 0));	
		
		int[] A = {0, 1, -1};
		int[] B = {-1, 1, 0};
		int[] C = {0, 0, 1};
		int[] D = {-1, 1, 1};
		Sum2Sum3Sum4 object = new Sum2Sum3Sum4();
		System.out.println(object.fourSumCount(A, B, C, D));
	}

	// hashmap中存储值到下标的映射
	//数组中可能有重复的数字
	public static int[] twoSum(int[] numbers, int target) {
		int[] result = new int[2];
		HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
		for (int i = 0; i < numbers.length; i++) {
			hash.put(numbers[i], i + 1);
		}
		int hashtemp;
		for (int i = 0; i < numbers.length; i++) {
			hashtemp = target - numbers[i];
			Integer index = hash.get(hashtemp);
			System.out.println("index" + index + " " + hashtemp);
			if (index != null && (index != (i + 1))) {
				result[0] = i + 1;
				result[1] = index;
				break;
			}
		}
		return result;
	}
	
	//以上的简化版本
	public static int[] twoSum2(int[] nums, int target) {
        if(nums == null || nums.length <= 0){
            return null;
        }
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0; i < nums.length; i++){
            map.put(nums[i], i);
        }
        Integer temp = 0;
        for(int i = 0; i < nums.length; i++){
            //temp != i 是为了解决重复数字相加的问题，比如8 = 4 + 4，若是只有一个4，则temp会等于i 
            if((temp = map.get(target - nums[i])) != null && temp != i){
                return new int[]{i, map.get(target - nums[i])};
            }
        }
        return new int[]{};
    }
	
	
	//3 sum，求可为0. 数组中可能有重复数字
	public static List<List<Integer>> threeSum(int[] nums){
		List<List<Integer>> lists = new ArrayList<List<Integer>>();
		if(nums == null || nums.length <= 0){
			return lists;
		}
		//first, we can sort first
		Arrays.sort(nums);
		//attention , we must to handle the duplicate problem
		for (int i = 0; i < nums.length - 1; i++) {
			int low = i + 1, high = nums.length - 1, sum = 0 - nums[i]; //this priblem is sum is 0
			//if the next elemnt of i is same as i, then we can know it is duplicate
			//因为数组是排好序的，所以当一个数被放到结果集中的时候，其后面和它相等的直接被跳过
			if(i == 0 || i > 0 && nums[i] != nums[i - 1]){
				//if the array is sorted, we can use two pointer, if sum is bigger, then move right pointer
				//if sum is smaller, then move left pointer
				while(low < high){
					if(nums[low] + nums[high] == sum){
						lists.add(Arrays.asList(nums[i], nums[low], nums[high]));
						while(low < high && nums[low] == nums[low + 1]) low++;
						while(low < high && nums[high] == nums[high - 1]) high--;
						//注意上面的判断条件是nums[low] == nums[low + 1]
						//跳出循环之后还需要再次移动
						low++;
						//wrong update in 2017/01/14
						//attention ,must move two, because we don't need the duplicate 
						high--;   
						
						//but how can we get the duplicate while low change and high does not change?
						//it's just faster than only move low!!! 
					}else if(nums[low] + nums[high] < sum){
						low++;
					}else{
						high--;
					}
				}
			}
		}
		return lists;
	}
	
	//3Sum clostest
    public static int threeSumClosest(int[] nums, int target) {
        if(nums == null || nums.length <= 2){
        	return (Integer)null;
        }
        Arrays.sort(nums);
        int closest = nums[0] + nums[1] + nums[2];  //intial the closest
        int low, high;
        for (int i = 0; i < nums.length - 1; i++) {
			low = i + 1; high = nums.length - 1; 
			//if the next elemnt of i is same as i, then we can know it is duplicate
			//因为数组是排好序的，所以当一个数被放到结果集中的时候，其后面和它相等的直接被跳过
			if(i == 0 || i > 0 && nums[i] != nums[i - 1]){
				//if the array is sorted, we can use two pointer, if is bigger, then move right pointer
				//if is smaller, then move left pointer
				while(low < high){
					if (nums[i] + nums[low] + nums[high] == target) {
						return target;
					}
					if(Math.abs(nums[low] + nums[high] + nums[i] - target) <= Math.abs(closest - target)){
						System.out.println("closest " + closest);
						closest = nums[low] + nums[high] + nums[i];
						System.out.println("closest change" + closest);
						while(low < high && nums[low] == nums[low + 1]) low++;
						while(low < high && nums[high] == nums[high - 1]) high--;
					}
					//Attention, this problem must judge each time, 而不是在上面的if中进行判断
					if(nums[low] + nums[high] + nums[i] < target){
						low++;
					}else{
						high--;
					}
				}
			}
		}
        return closest;
    }
    
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> lists = new ArrayList<List<Integer>>();
		if(nums == null || nums.length <= 0){
			return lists;
		}
		//first, we can sort first
		Arrays.sort(nums);
		//attention , we must to handle the duplicate problem
		
		int sum3 = 0;
		for(int k = 0; k < nums.length - 1; k++){
			sum3 = target - nums[k];
			if(k == 0 || k > 0 && nums[k] != nums[k - 1]){
				for (int i = k + 1; i < nums.length - 1; i++) {
					int low = i + 1, high = nums.length - 1, sum2 = sum3 - nums[i]; //this priblem is sum is 0
					//if the next elemnt of i is same as i, then we can know it is duplicate
					//因为数组是排好序的，所以当一个数被放到结果集中的时候，其后面和它相等的直接被跳过
					if(i == k + 1 || i > 0 && nums[i] != nums[i - 1]){
						//if the array is sorted, we can use two pointer, if is bigger, then move right pointer
						//if is smaller, then move left pointer
						while(low < high){
							if(nums[low] + nums[high] == sum2){
								lists.add(Arrays.asList(nums[k],nums[i], nums[low], nums[high]));
								while(low < high && nums[low] == nums[low + 1]) low++;
								while(low < high && nums[high] == nums[high - 1]) high--;
								low++;
								high--;   //attention ,must move two, because we don't need the duplicate
							}else if(nums[low] + nums[high] < sum2){
								low++;
							}else{
								high--;
							}
						}
					}
				}
			}
		}
		return lists;
    }
    
    
    //4SumII,给定四个list，分别找到四个下标i，j，k，L，使得满足四个数相加得sum
    //返回有多少种可能 how many tuples (i, j, k, L)
    
    //超时了
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
    	//存储该数字出现的次数
    	HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
		for (int i = 0; i < D.length; i++) {
			hash.put(D[i], hash.getOrDefault(D[i], 0) + 1);
		}
		Arrays.sort(A);
		Arrays.sort(B);
		Arrays.sort(C);
		Arrays.sort(D);
		int res = 0;
		int last = 0;
		for (int i = 0; i < A.length; i++) {
			int temp = res;
			if(i != 0 && A[i] == A[i - 1]){
				res += last;
				continue;
			}
			int lastB = 0;
			for (int j = 0; j < B.length; j++) {
				int tempB = res;
				if(j != 0 && B[j] == B[j - 1]){
					res += lastB;
					continue;
				}
				int lastC = 0;
				for (int k = 0; k < C.length; k++) {
					int tempC = res;
					if(k != 0 && C[k] == C[k - 1]){
						res += lastC;
						continue;
					}
					int desire = -A[i] - B[j] - C[k];
					System.out.println("desire: " + desire);
					Integer times;
					if ((times = hash.get(desire)) != null) {
						res += times;
					}
					lastC = res - tempC;
				}
				lastB = res - tempB;
			}
			last = res - temp;
		}
		return res;
    }
    
    //先求A 与 B相加的所有和，然后判断相反数是否在C 和 D的和中
    //点get到了，但是实现仍然是O(n ^ 3)
    //仍然超时了
    public int fourSumCount_2(int[] A, int[] B, int[] C, int[] D) {
    	Arrays.sort(A);
		Arrays.sort(B);
		Arrays.sort(C);
		Arrays.sort(D);
		
		HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
		for (int i = 0; i < D.length; i++) {
			hash.put(D[i], hash.getOrDefault(D[i], 0) + 1);
		}
		int res = 0;
		
		int[] sum = new int[A.length * A.length];
		int index = 0;
    	for (int i = 0; i < A.length; i++) {
			for (int j = 0; j < B.length; j++) {
				sum[index++] = A[i] + B[j];
			}
    	}
    	
    	Arrays.sort(sum);
    	int last = 0;
    	for (int i = 0; i < sum.length; i++) {
    		int temp = res;
			if(i != 0 && A[i] == A[i - 1]){
				res += last;
				continue;
			}
			res += twoSumCount(C, hash, -sum[i]);
			last = res - temp;
		}
    	return res;
    }
    
    public int twoSumCount(int[] C, HashMap<Integer, Integer> map, int target){
    	int res = 0;
    	int last = 0;
    	for (int i = 0; i < C.length; i++) {
    		int temp = res;
			if(i != 0 && C[i] == C[i - 1]){
				res += last;
				continue;
			}
			Integer times;
			if ((times = map.get(target - C[i])) != null) {
				res += times;
			}
			last = res - temp;
    	}
    	return res;
    }
    
    //上述的关键是sum会很大，我们无法枚举sum然后sum是否在A，B  以及-sum在C、D
    //假设sum 在-100 ~ 100
    //那么可以想到i from : -100 to 100,然后O(n^ 2)判断sum是否在A、B中，O(n ^ 2)-sum是否在C、D中
    //好了说了这么多，想到啥没有啊
    //对，map,反正长度限制在500以内，我们将所有A和B的sum存放咋hashmap中，然后O(n ^ 2)判断C、D是否有-sum
    
    public int fourSumCount_3(int[] A, int[] B, int[] C, int[] D) {
    	int sum = 0;
    	HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
    	for (int i = 0; i < A.length; i++) {
			for (int j = 0; j < B.length; j++) {
				sum = A[i] + B[j];
				hash.put(sum, hash.getOrDefault(sum, 0) + 1);
			}
    	}
    	int res = 0;
    	for (int i = 0; i < C.length; i++) {
			for (int j = 0; j < D.length; j++) {
				Integer times;
				if ((times = hash.get(-D[j] - C[i])) != null) {
					res += times;
				}
			}
    	}
    	return res;
    }
}
